import java.math.BigInteger;
import java.util.HashMap;
import java.util.StringTokenizer;


class P10229_39643 {
	
	static BigInteger TWO = new BigInteger("2");
	
	public static void main(String[] args) {
		String line = readLn();
		
		
		BigInteger[] mods = new BigInteger[21];
		
		for (int k = 0; k < 21; k++) {
			mods[k] = TWO.pow(k);
		}
		
//		HashMap<BigInteger, BigInteger> fibs = new HashMap<BigInteger, BigInteger>();
		
		while (line != null) {
			StringTokenizer st = new StringTokenizer(line);
			int nI = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			BigInteger n = new BigInteger(Integer.toString(nI));
//			BigInteger fib = fibs.get(n);
			
//			if (fib == null) {
				BigInteger fib = getFib(n, mods[m]);
//				fibs.put(mod, fib);
//			}
			
			System.out.println(fib.mod(mods[m]));
			
			line = readLn();
		}
	}
	
//	   Fib3(n)
//       i := 1
//       j := 0
//       k := 0
//       h := 1
//       while n > 0 do
//          if n is odd then
//             t := jh
//             j := ih + jk + t
//             i := ik + t
//          t := h2
//          h := 2kh + t
//          k := k2 + t
//          n := floor( n/2 )
//       return j

	
	private static BigInteger getFib(BigInteger n, BigInteger mod) {
		
		BigInteger i = BigInteger.ONE;
		BigInteger j = BigInteger.ZERO;
		BigInteger k = BigInteger.ZERO;
		BigInteger h = BigInteger.ONE;
		BigInteger t;
		while (n.compareTo(BigInteger.ZERO) > 0) {
			if (n.mod(TWO).equals(BigInteger.ONE)) {
				t = j.multiply(h) /**/ .mod(mod) ;
				j = ((i.multiply(h).mod(mod)) .add( (j.multiply(k)).mod(mod) ) .add( t.mod(mod) )).mod(mod);
				i = i.multiply(k) .add( t );
			}
			
			t = h.pow(2) /* */ .mod(mod);
			h = (TWO.multiply(k).multiply(h)) .add( t );
			k = (k.pow(2).mod(mod) .add(t.mod(mod))   ).mod(mod);    //k.pow(2)  .add( t ); 
			n = n.shiftRight(1);
			
		}
		
		return j;
	}

	static String readLn() {
		String newLine = System.getProperty("line.separator");
		StringBuilder buffer = new StringBuilder();
		int car = -1;
		try {
			car = System.in.read();
			while ((car > 0) && (car != newLine.charAt(0))) {
				buffer.append((char) car);
				car = System.in.read();
			}
			if (car == newLine.charAt(0))
				System.in.skip(newLine.length() - 1);
		} catch (java.io.IOException e) {
			return (null);
		}
		if ((car < 0) && (buffer.length() == 0))
			return (null);
		return (buffer.toString());
	}
}
